package problem;

import java.util.Stack;

public class S_114 {
    //二叉树展开为链表
    //起始就是先序遍历，但是要求原地算法
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    //1.找到左子树最右边的结点以便和右子树连接起来
    class Solution {
        public void flatten(TreeNode root) {
            while(root!=null){
                if(root.left==null) root=root.right;    //左子树为空，直接考虑下一个节点
                else{
                    //左子树存在就找到最左子树最右边的结点
                    TreeNode pre=root.left;
                    while(pre.right!=null) pre=pre.right;//pre结束的位置就是左子树的最右边的节点
                    //将原来右子树接到左子树最右节点右边
                    pre.right=root.right;
                    //将左子树接到右子树的地方
                    root.right=root.left;
                    root.left=null;
                    root=root.right;    //考虑下一个节点
                }
            }
        }
    }
    //2.递归的后序遍历
    class Solution1{
        private TreeNode pre=null;
        public void flatten(TreeNode root){
            if(root==null) return;
            flatten(root.right);
            flatten(root.left);
            root.right=pre;
            root.left=null;
            pre=root;
        }
    }

    //3.迭代的后序遍历
    class Solution2{
        public void flatten(TreeNode root) {
            Stack<TreeNode> toVisit = new Stack<>();
            TreeNode cur = root;
            TreeNode pre = null;

            while (cur != null || !toVisit.isEmpty()) {
                while (cur != null) {
                    toVisit.push(cur); // 添加根节点
                    cur = cur.right; // 递归添加右节点
                }
                cur = toVisit.peek(); // 已经访问到最右的节点了
                // 在不存在左节点或者右节点已经访问过的情况下，访问根节点
                if (cur.left == null || cur.left == pre) {
                    toVisit.pop();
                    /**************修改的地方***************/
                    cur.right = pre;
                    cur.left = null;
                    /*************************************/
                    pre = cur;
                    cur = null;
                } else {
                    cur = cur.left; // 左节点还没有访问过就先访问左节点
                }
            }
        }
    }
    //4.修改后的先序遍历
    class Solution3{
        public void flatten(TreeNode root) {
            if (root == null){
                return;
            }
            Stack<TreeNode> s = new Stack<TreeNode>();
            s.push(root);
            TreeNode pre = null;
            while (!s.isEmpty()) {
                TreeNode temp = s.pop();
                /***********修改的地方*************/
                if(pre!=null){
                    pre.right = temp;
                    pre.left = null;
                }
                /********************************/
                if (temp.right != null){
                    s.push(temp.right);
                }
                if (temp.left != null){
                    s.push(temp.left);
                }
                /***********修改的地方*************/
                pre = temp;
                /********************************/
            }
        }
    }
}
